﻿// 0929train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <numeric>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
给定一个以顺序储存结构存储整数值的完全二叉树序列（最多1000个整数）
请找出此完全二叉树的所有非叶子节点部分，然后采用后序遍历方式将此部分树（不包含叶子）输出
1、只有一个节点的树，此节点认定为根节点（非叶子）。
2、此完全二叉树并非满二叉树，可能存在倒数第二层出现叶子或者无右叶子的情况
其他说明：二叉树的后序遍历是基于根来说的，遍历顺序为：左-右-根

输入描述
一个通过空格分割的整数序列字符串

输出描述
非叶子部分树结构

输入
1 2 3 4 5 6 7
输出
2 3 1
 */
class Solution01
{
public:
    struct TreeNode
    {
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode() = default;
        TreeNode(int val) : val(val) {};
        TreeNode(int val, TreeNode* left, TreeNode* right) :val(val), left(left), right(right) {};
    };
    TreeNode* buildTree(vector<int>& num_vec, int index)
    {
        int val = num_vec[index];
        int v_size = num_vec.size();
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        if (2*index+1<v_size)
        {
            left = buildTree(num_vec, 2 * index + 1);
        }
        if (2*index+2<v_size)
        {
            right = buildTree(num_vec, 2 * index + 2);
        }
        return new TreeNode(val, left, right);
	    //buildTree
    }

    void postOrder(TreeNode* node, vector<int>&result)
    {
        if (node == nullptr) return;

        postOrder(node->left, result);
        postOrder(node->right, result);

        if (node->left == nullptr && node->right == nullptr)
            return;
        //非叶子部分树结构
        result.push_back(node->val);
	    //postOrder
    }

    Solution01(vector<int>&num_vec)
    {
        if (num_vec.size()==1)
        {
            cout << num_vec[0];
            return;
        }

        TreeNode* root = buildTree(num_vec, 0);

        vector<int>result;
        postOrder(root, result);

        for (auto&item:result)
        {
            cout << item << ' ';
        }

	    //Solution01
    }
};


/*
 定义构造三叉搜索树规则如下：
每个节点都存有一个数，当插入一个新的数时，从根节点向下寻找，直到找到一个合适的空节点插入。
查找的规则是： 
1. 如果数小于节点的数减去 500，则将数插入节点的左子树 
2. 如果数大于节点的数加上 500，则将数插入节点的右子树 
3. 否则，将数插入节点的中子树
给你一系列数，请按以上规则，按顺序将数插入树中，构建出一棵三叉搜索树，最后输出树的高度。
输入描述
第一行为一个数 N，表示有 N 个数，1 <= N <= 10000
第二行为 N 个空格分隔的整数，每个数的范围为[1, 10000]
输出描述
输出树的高度(根节点的高度为 1)
示例一
5
5000 2000 5000 8000 1800
输出
3
 */
class Solution02
{
public:
    struct TreeNode
    {
        int val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;
        TreeNode* middle = nullptr;
        TreeNode() = default;
        TreeNode(int val) : val(val) {};
    };

    void insertNode(TreeNode*root, TreeNode*node)
    {
        //数小于节点的数减去 500 插入左
        //数大于节点的数加上 500 插入右
        //插入中

        while (root)
        {
            if (node->val < root->val-500)
            {
	            if (root->left==nullptr)
	            {
                    root->left = node;
                    break;
	            }
                root = root->left;
            }
			else if (node->val > root->val+500)
            {
                if (root->right==nullptr)
                {
                    root->right = node;
                    break;
                }
                root = root->right;
            }
            else
            {
                if (root->middle==nullptr)
                {
                    root->middle = node;
                    break;
                }
                root = root->middle;
            }
	        //while
        }
	    //insertNode
    }

    void bfs(TreeNode* root)
    {
        deque<TreeNode*>bfs_queue;
        bfs_queue.push_back(root);

        while (!bfs_queue.empty())
        {
            result++;
            int q_size = bfs_queue.size();
            for (int i=0; i<q_size; i++)
            {
                TreeNode* top_node = bfs_queue.front();
                bfs_queue.pop_front();

                if (top_node->left!=nullptr)
                {
                    bfs_queue.push_back(top_node->left);
                }

                if (top_node->right!=nullptr)
                {
                    bfs_queue.push_back(top_node->right);
                }

                if (top_node->middle!=nullptr)
                {
                    bfs_queue.push_back(top_node->middle);
                }

	            //for---
            }

	        //while--
        }


	    //bfs
    }


    Solution02(vector<int>&num_vec)
    {
        TreeNode* root = new TreeNode(num_vec[0]);

        int v_size = num_vec.size();
        for (int i=1; i<v_size; i++)
        {
            TreeNode* node = new TreeNode(num_vec[i]);
            insertNode(root, node);
        }
        bfs(root);

        cout << result;

	    //Solution02
    }
private:
    int result = 0;
};


/*
某文件系统中有N个目录，每个目录都有一个独一无二的ID。
每个目录只有一个父目录，但每个父目录下可以有零个或者多个子目录，目录结构呈树状结构。

假设，根目录的ID为0，且根目录没有父目录，其他所有目录的ID用唯一的正整数表示，并统一编号。
现给定目录ID和其父目录ID的对应父子关系表[子目录ID，父目录ID]，
以及一个待删除的目录ID，
请计算并返回一个ID序列，表示因为删除指定目录后剩下的所有目录，返回的ID序列以递增序输出。
注意：
1、被删除的目录或文件编号一定在输入的ID序列中；
2、当一个目录删除时，它所有的子目录都会被删除。
输入描述：
输入的第一行为父子关系表的长度m；
接下来的m行为m个父子关系对；
最后一行为待删除的ID。序列中的元素以空格分割，参见样例。

输出描述：输出一个序列，表示因为删除指定目录后，剩余的目录ID。
示例1
输入
5
8 6
10 8
6 0
20 8
2 6
8
输出
2 6

子目录ID，父目录ID
子目录都会一起被删除

删除指定目录后剩下的所有目录
返回的ID序列以递增序输出
 */
class Solution03
{
public:
    Solution03(vector<vector<int>>&link_vec, int first_i)
    {
        unordered_map<int, vector<int>>link_map;
        unordered_set<int>node_set;

        for (auto&item:link_vec)
        {
            //子ID 父ID
            link_map[item[1]].push_back(item[0]);
            node_set.insert(item[0]);
            node_set.insert(item[1]);

	        //for---
        }

        deque<int>bfs_queue;
        bfs_queue.push_back(first_i);
        while (!bfs_queue.empty())
        {
            int top_i = bfs_queue.front();
            bfs_queue.pop_front();
            node_set.erase(top_i);

            if (link_map.count(top_i) == 0) continue;

            vector<int>child_v = link_map.at(top_i);

            for (auto&child: child_v)
            {
	            if (node_set.count(child)>0)
	            {
                    bfs_queue.push_back(child);
	            }
            }

	        //while---
        }

        //去掉根目录
        node_set.erase(0);
        vector<int>result;
        for (auto&node:node_set)
        {
            result.push_back(node);
        }
        sort(result.begin(), result.end());

        for (auto&item:result)
        {
            cout << item << ' ';
        }
	    //Solution03
    }
};

int main()
{
	{
        int v_size;
        cin >> v_size;
        vector<vector<int>>link_vec(v_size);

        for (int i=0; i<v_size; i++)
        {
            vector<int>item(2);
            cin >> item[0] >> item[1];
            link_vec[i] = item;
        }
        int first_i;
        cin >> first_i;

        Solution03 solu(link_vec, first_i);

        return 0;
	}
	{
        int v_size;
        cin >> v_size;
        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }
        Solution02 solu(num_vec);

        return 0;
	}
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    vector<int>num_vec;
    while (oh_sstream >> token)
    {
        num_vec.push_back(stoi(token));
    }

    Solution01 solu(num_vec);

    //main---
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
